package ocm.oh.ds;

import java.util.ArrayList;
import java.util.Random;

public class DS {
    private int[][] initialColumns = null;
    //private int[][] columns = null;
    
    private int[] queens = null;
    private int[] initialQueens = null;
    private ArrayList<State> lastStates = new ArrayList<State>();
    
    private Random rndMinConflictIndex = new Random(8174587328732L);
    int nrOfMoves = 0;
    
    public DS(int size) {
        
        initialQueens = new int[size];
        
        Random rnd = new Random();
        for(int row=0; row < initialQueens.length; row++) {
            int rndColumnIndexForQueen = rnd.nextInt(size);
            initialQueens[row] = rndColumnIndexForQueen;
        }
                
        queens = initialQueens.clone();
        
        initialColumns = new int[size][size];
        
        //addToLastStates(queens);
        
        // columns[0] is the first row (with another array of columns)
        // columns[1] is the second row...
        // so;  columns[0][3] would be first row, fourth cell
        
        /*
        for(int row=0; row < initialColumns.length; row++) {
            int rndIndexForQueen = rnd.nextInt(size);
            initialColumns[row][rndIndexForQueen] = 1;
        }  */
        
        /*
        columns = initialColumns.clone();
        for(int i=0; i < initialColumns.length; i++) {
            columns[i] = initialColumns[i].clone();
        }
        */
        
        // QueenGui queenGui = new QueenGui("Initial State", initialQueens);
    }
    
    public SolutionState doDumbSearch(int maxIterations) {
        long startTime = System.currentTimeMillis();
        int iterations = 0;
        int size = queens.length;
        Random rnd = new Random();
        while(iterations < maxIterations && !isSolution()) {
        	//printQueens();
            iterations++;
            int queen = rnd.nextInt(size);
            // Get the min-violations-index
            //int queenColumnIndex = getQueenColumnIndex(queen);
            int queenColumnIndex = queens[queen];
            
            // System.out.println("Queen index for queen: " + queen +  " : "  + getQueenColumnIndex(queen));
            int columnToMoveTo = getMinConflictsColumn(queen, queenColumnIndex);            
            if(columnToMoveTo > -1) {
                // System.out.println("Queen " + queen + " from " + queenColumnIndex + " to " + columnToMoveTo);
                queens[queen] = columnToMoveTo;
                //columns[queen][queenColumnIndex] = 0;
                //columns[queen][columnToMoveTo] = 1;
                nrOfMoves++;        
                addToLastStates(queens);
               //printQueens();
            }
           // if(true) return columns;
        }
        //print solution state to console
        //printQueens();
        long runTimeInMs = System.currentTimeMillis() - startTime;

        printLastStates();
        
        return new SolutionState(queens.length, queens, iterations, nrOfMoves, runTimeInMs, isSolution());
    }
        
    private boolean isSolution() {
        for(int row=0; row < queens.length; row++) {
            if(getViolationsIfMovedHere(queens[row], row) > 0) return false;
            //
            //for(int column=0; column < columns.length; column++) {
            //    if(columns[row][column] == 1) {
            //       if(getViolationsIfMovedHere(column, row) > 0) return false;
            //    }
           // }
        }
        //System.out.println("Is solution!");
        return true;
    }    
    
    /*
    private int getQueenColumnIndex(int queen) {
        int queenColumnIndex = 0;
        for(int i=0; i < columns.length; i++) {
            if(columns[queen][i] == 1) {
                queenColumnIndex = i;
                break;
            }
        }
        return queenColumnIndex;
    }
    */
   
    
    private int getViolationsIfMovedHere(int x, int queen) {
        int count = 0;
        for(int i=0; i < queens.length; i++) {
            if(i != queen) {
                if(queens[i] == x) count++;
                else if(queens[i] == x + Math.abs(queen-i)) count++;
                else if(queens[i] == x - Math.abs(queen-i)) count++;
                //else if(x - Math.abs(x-queens[i]) == queens[i]) count++;
            }
        }        
        return count;
    }
    
    /*
    private int getViolationsIfMovedHere(int x, int y) {
        int count = 0;
        count += getCount(x, y, 1, 1); // diagonal down-right
        count += getCount(x,y,-1,-1); // diagonal up-left
        
        count += getCount(x, y, 1, -1); // up-right
        count += getCount(x,y,-1,1); // down-left        
        count += getCount(x,y,0,1); // Down
        count += getCount(x,y,0,-1); // Up       
        
        count += getCount(x,y,1,0); // right
        count += getCount(x,y,-1,0); // left
        
        return count;
    }
    */
    
    private void getViolations(int x, int y) {
        // System.out.println("Violations for : (" + x + "," + y + ")" + getViolationsIfMovedHere(x, y));
    }
    
    /**
     *  Returns -1 if it should not move, or an integer >= 0 if it should move
     * @param queen
     * @return int column to move to
     */
    private int getMinConflictsColumn(int queen, int queenColumnIndex) {
        int[] violations = new int[queens.length]; 
        for(int i=0; i < queens.length; i++) {
            violations[i] = getViolationsIfMovedHere(i, queen);
        }   
        int minConflictIndex = 0;        
        ArrayList<Integer> minConflicts = new ArrayList<Integer>();
 
        int lowestValue = getViolationsIfMovedHere(queenColumnIndex,queen);               
        for(int i=0; i < violations.length; i++) {
            if(violations[i] < lowestValue && i != queenColumnIndex) lowestValue = violations[i];
        }        
        for(int i=0; i < violations.length; i++) {
            // Get all the violations with lowest value, and add them to the arraylist
            if(violations[i] == lowestValue && i != queenColumnIndex) minConflicts.add(i);
        }        
        
        if(minConflicts.size() > 0) {            
            return minConflicts.get(rndMinConflictIndex.nextInt(minConflicts.size()));
        }        
        return -1;
    }
    
    /*
    private int getCount(int x,int y, int dX, int dY) {
        int curX = x;
        int curY = y;              
        int count = 0;
       // curX += dX;
       // curY += dY;
        while(curX >= 0 && curX < columns[0].length && curY >= 0 && curY < columns.length) {
            if(columns[curY][curX] == 1 && curY != y) count++;
            // System.out.println("Checking cell: Y: " + curY + " X: " + curX);
            curX += dX;
            curY += dY;
        }
        return count;
    }  
    */    
    private void printLastStates(){
        for (int i=0; i<lastStates.size();i++){
        	printBoard(lastStates.get(i).getQueens());
        	System.out.println("Number of attacks :"+ lastStates.get(i).getViolations() + "\n");
        }
    }
    
    private void printBoard(int[] board){
    	
    	int[][] twoDimQueens = new int[board.length][board.length];
    	
    	for (int i=0; i<board.length;i++){
    		twoDimQueens[i][board[i]] = 1;
    	}
    	
    	for (int i=0;i<twoDimQueens.length;i++){
    		for (int j=0;j<twoDimQueens.length;j++){
    			System.out.print(twoDimQueens[i][j]+"   ");
    		}
    		System.out.print("\n");
    	}
    }
    
    private void printQueens(){
    	
    	int[][] twoDimQueens = new int[queens.length][queens.length];
    	
    	for (int i=0; i<queens.length;i++){
    		twoDimQueens[i][queens[i]] = 1;
    	}
    	
    	for (int i=0;i<twoDimQueens.length;i++){
    		for (int j=0;j<twoDimQueens.length;j++){
    			System.out.print(twoDimQueens[i][j]+" ");
    		}
    		System.out.print("\n");
    	}
    	System.out.print("\n");
    }
    
    private synchronized void addToLastStates(int[] board){    	
    	State state = new State(board);
    	if (lastStates.size() >=5) lastStates.remove(0);
    	lastStates.add(state);
    }
}
